package com.zjj.algorithm.learning.leetcode.tree;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 222. 完全二叉树的节点个数 中档题
 * <p>
 * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
 * <p>
 * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
 * <p>
 * 输入：root = [1,2,3,4,5,6]
 * 输出：6
 * 示例 2：
 * <p>
 * 输入：root = []
 * 输出：0
 * 示例 3：
 * <p>
 * 输入：root = [1]
 * 输出：1
 * <p>
 * <p>
 * 提示：
 * <p>
 * 树中节点的数目范围是[0, 5 * 104]
 * 0 <= Node.val <= 5 * 104
 * 题目数据保证输入的树是 完全二叉树
 *
 * @author zjj_admin
 * @date 2022/12/20 10:38
 */
public class CountCompleteTreeNodes {

    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;

        int res = countNodes2(node1);
        System.out.println("res = " + res);

    }


    /**
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 44.3 MB
     * 击败
     * 33.5%
     *
     * @param root
     * @return
     */
    public static int countNodes2(TreeNode root) {
        TreeNode l = root, r = root;
        int lh = 0, rh = 0;
        while (l != null) {
            l = l.left;
            lh++;
        }
        while (r != null) {
            r = r.right;
            rh++;
        }
        if (lh == rh) {
            return (int) Math.pow(2, lh) - 1;
        }
        return countNodes2(root.left) + countNodes2(root.right) + 1;
    }


    /**
     * 时间
     * 4 ms
     * 击败
     * 19.71%
     * 内存
     * 44.4 MB
     * 击败
     * 21.79%
     *
     * @param root
     * @return
     */
    public static int countNodes(TreeNode root) {

        if (root == null) {
            return 0;
        }
        if (root.left == null) {
            return 1;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        int res = 0;
        queue.add(root);
        res++;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.add(poll.left);
                    res++;
                }
                if (poll.right != null) {
                    queue.add(poll.right);
                    res++;
                }
            }
        }
        return res;
    }
}
